package com.chao.stucture.list;

import java.io.Serializable;

/**
 * @author : Rookie
 * @description : 带虚拟头节点的单链表
 * @date : 2022/11/14
 */
public class SingLinkedListWithDummyHead<E> {

    /**
     * 链表大小
     */
    private int size;
    /**
     * 虚拟头节点
     */
    private Node dummyHead;

    public SingLinkedListWithDummyHead() {
        this.dummyHead = new Node();
    }


    class Node implements Serializable {
        /**
         * 元素
         */
        private E element;
        /**
         * 指向下一个节点
         */
        private Node next;

        public Node() {

        }

        public Node(E element) {
            this.element = element;
        }
    }

    public E get(int index) {
        if ( index < 0 || index >= size) {
            throw new RuntimeException("链表越界！");
        }
        Node currNode = dummyHead;
        while (index > 0) {
            currNode = currNode.next;
            index --;
        }
        return currNode.element;
    }

    /**
     * 头插法
     * @param e
     */
    public void addAtHead(E e) {
        addAtIndex(0,e);
    }

    /**
     * 尾插法
     * @param e
     */
    public void addAtTail(E e) {
        addAtIndex(size,e);
    }

    /**
     * 在指定索引处添加元素
     * @param index 索引
     * @param e 元素
     */
    public void addAtIndex(int index,E e) {
        if (index < 0 || index > size) {
            throw new RuntimeException("索引越界！");
        }
        Node newNode = new Node(e);
        Node currNode = dummyHead;
        while (index > 0) {
            currNode = currNode.next;
            index --;
        }

        newNode.next = currNode.next;
        currNode.next = newNode;
        size ++;
    }

    /**
     * 移除索引处的元素
     * @param index
     */
    public void remove(int index) {
        if (index < 0 || index > size - 1) {
            throw new RuntimeException("索引越界！");
        }

        Node currNode = dummyHead;
        while (index > 0) {
            currNode = currNode.next;
            index --;
        }
        currNode.next = currNode.next.next;
        size --;
    }

    public void display(){
        StringBuffer sb = new StringBuffer();
        Node currentNode = dummyHead.next;
        while (currentNode != null){
            if (currentNode.next != null) {
                sb.append(currentNode.element).append("->");
            } else {
                sb.append(currentNode.element);
            }
            currentNode = currentNode.next;
        }
        System.out.print(sb);
    }

    /**
     * 反转链表 双指针法
     */
    public void reverseListByTwoPointer() {
        Node currNode = dummyHead.next;
        Node preNode = null;
        while (currNode != null) {
            //先临时保存下一节点
            Node tempNode = currNode.next;
            //将本节点指向上一节点
            currNode.next = preNode;
            //指针后移
            preNode = currNode;
            currNode = tempNode;
        }
        assert preNode != null;
        //最后将原链表的虚拟头节点指向链表的最后一个节点
        dummyHead.next = preNode;
    }

    /**
     * 反转链表 递归法
     */
    public void reverseListByRecursive() {
        reverseList(dummyHead.next,null);
    }

    public int size() {
        return this.size;
    }

    /**
     * 递归法反转单链表
     * @param currNode 当前节点
     * @param preNode 上一节点
     */
    private void reverseList(Node currNode,Node preNode) {
        if (currNode == null) {
            //最后将原链表的虚拟头节点指向链表的最后一个节点
            dummyHead.next = preNode;
            return;
        }
        //临时保存下一节点
        Node tempNode = currNode.next;
        //将本节点指向上一节点
        currNode.next = preNode;
        //指针后移
        preNode = currNode;
        currNode = tempNode;
        reverseList(currNode, preNode);
    }

    /**
     * 交换链表节点
     */
    private void swapNode() {
        //当前节点指向虚拟头节点 操作第一个和第二个节点
        Node currNode = dummyHead;
        Node tempNode;
        Node tempNode1;
        while (currNode.next != null && currNode.next.next != null) {
            //交换之前保存指针
            tempNode = currNode.next;
            tempNode1 = currNode.next.next.next;
            //将指针指到原来的第二个节点
            currNode.next = currNode.next.next;
            //将原来第一个节点赋值到第二个节点
            currNode.next.next = tempNode;
            //将第一个节点赋值到第三个节点
            tempNode.next = tempNode1;
            //移动curr指针
            currNode = currNode.next.next;
        }
    }


    /**
     * 链表长度为L
     * 快指针先走k步 慢指针开始走
     * 慢指针移动L-k 所在节点即为要删除的节点
     * 移除链表到处第n个节点
     * @param n 第n个
     */
    private void removeReciprocalN(int n) {
        if (n < 0 || n > size - 1) {
            throw new RuntimeException("索引越界！");
        }
        Node fast = dummyHead;
        Node low = dummyHead;

        while (n >= 0) {
            fast = fast.next;
            n--;
        }

        while (fast != null) {
            low = low.next;
            fast = fast.next;
        }
        assert low != null;
        low.next = low.next.next;
    }

    /**
     * 获取环形链表入口
     * 设链表环形链表入口之前长度为x 入口到快慢指针相遇处长度为y 相遇处到环形链表出口处长度为z
     * 设慢指针速度为v 快指针速度为2v
     * 可得 2（x+y）= x+y+n(y+z) 化简得 x=(n-1)(y+z) + z (n>=1)
     * 定义一个指针从头节点开始 另一个从相遇点开始 则他们相遇得地方就是环的入口处
     * @return
     */
    public Node getCircleListEntrance() {
        Node fast = dummyHead.next;
        Node slow = dummyHead.next;
        Node circleEntrance = null;
        while (fast != null && fast.next != null) {
            fast = fast.next.next;
            slow = slow.next;
            //此时快慢指针相遇
            if (fast.equals(slow)) {
                Node index1 = dummyHead.next;
                Node index2 = fast;
                while (!index1.equals(index2)) {
                    index1 = index1.next;
                    index2 = index2.next;
                }
                circleEntrance = index1;
            }
        }
        return circleEntrance;
    }

    public static void main(String[] args) {
        SingLinkedListWithDummyHead<String> listWithDummyHead = new SingLinkedListWithDummyHead<>();
        listWithDummyHead.addAtHead("A");
        listWithDummyHead.addAtHead("B");
        listWithDummyHead.addAtIndex(1, "C");
        System.out.print("链表反转前：");
        listWithDummyHead.display();
        System.out.println();
//        System.out.print("==============双指针法反转单链表====================");
//        listWithDummyHead.reverseListByTwoPointer();
//        System.out.println();
//        System.out.println("链表反转后：");
//        listWithDummyHead.display();
//        System.out.println("=================递归法反转单链表===================");
//        listWithDummyHead.reverseListByRecursive();
//        listWithDummyHead.display();
//        System.out.println("=================单链表两两节点交换===================");
//        listWithDummyHead.swapNode();
//        listWithDummyHead.display();
        listWithDummyHead.addAtHead("D");
        listWithDummyHead.addAtTail("S");
        listWithDummyHead.display();
        listWithDummyHead.removeReciprocalN(2);
        System.out.println();
        listWithDummyHead.display();
    }
}
